Logger Rate Limiter

Try to solve the Logger Rate Limiter problem.

Statement#

For the given stream of message requests and their timestamps as input, you must implement a logger rate limiter system that decides whether the current message request is displayed. The decision depends on whether the same message has already been displayed in the last SS seconds. If yes, then the decision is FALSE, as this message is considered a duplicate. Otherwise, the decision is TRUE.

Note: Several message requests, though received at different timestamps, may carry identical messages.

Constraint:

  • Timestamps are in ascending order.

Examples#

Note: In the following examples, the time limit, SS, is set to 77.

Created with Fabric.js 3.6.6

1 of 3

Created with Fabric.js 3.6.6

2 of 3

Created with Fabric.js 3.6.6

3 of 3

Understand the problem#

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Logger Rate Limiter

2

Suppose the time limit for the following timestamps is 5. What will be the correct output sequence?

Your Answer
A)

TRUE
TRUE
TRUE
FALSE
TRUE
FALSE

Explanation

The first two requests will be accepted as they have different messages.

The third request “okayy” will be accepted as well, because 15 - 2 = 13 exceeds the time limit of 5 seconds. So, TRUE is returned.

The decision is FALSE for the fourth request “okayy”, because 16 - 15 = 1, which is less than the time limit of 5 seconds.

The fifth request “good” will be accepted as well, because 17 - 8 = 9, which exceeds the time limit of 5 seconds. So, TRUE is returned.

The sixth request “okayy” will be declined, because 20 - 16 = 4, which is less than the time limit of 5 seconds.

B)

TRUE
TRUE
FALSE
FALSE
TRUE
FALSE

C)

TRUE
TRUE
TRUE
FALSE
TRUE
TRUE

Question 2 of 22 attempted

Figure it out!#

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Drag and drop the cards to rearrange them in the correct sequence.

Use all incoming messages as keys and their respective timestamps as values, to form key-value pairs to store them in a hash map.

When a request arrives, use the hash map to check if it’s a new request or a repeated request. If it’s a new request, accept it and add it to the hash map.

If it’s a repeated request, check if SS seconds have passed since the last request with the same message. If this is the case, accept it and update the timestamp for that specific message in the hash map.

If the repeated request has arrived before the time limit has expired, reject it.


Try it yourself#

Implement your solution in the following coding playground:

Note: In the following test cases, the time limit, SS, is set to 77.

Python
usercode > request_logger.py
Powered by AI
Input #1
Logger Rate Limiter

Solution: Fraction to Recurring Decimal

Solution: Logger Rate Limiter